package com.hyper_yang.algorithmRecord.dynamicProgramming;

// leetcode 198 打家劫舍
public class LeetCode_198 {
    /*
    你是一个专业的小偷，计划偷窃沿街的房屋。
    每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
    如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
    给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
     */
    public int rob1(int[] nums) {
        int n = nums.length;
        // 定义状态，将前 i个房屋能偷到的最大金额保存到 dp[i]
        int[] dp = new int[n + 1];
        // 定义初始状态
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            // 考虑偷或者不偷第 n间房
            dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
        }
        return dp[n];
    }

    // 尝试空间优化
    public int rob(int[] nums) {
        int n = nums.length;
        int pre2 = 0; // 前两间
        int pre1 = nums[0]; // 前一间
        for (int i = 1; i < n; i++) {
            int maxRob = Math.max(pre2 + nums[i], pre1);
            pre2 = pre1;
            pre1 = maxRob;
        }
        return pre1;
    }

    public static void main(String[] args) {
        LeetCode_198 solution = new LeetCode_198();
        System.out.println(solution.rob(new int[]{1, 2, 3, 1})); // 4
        System.out.println(solution.rob(new int[]{2, 7, 9, 3, 1})); // 12
    }

}
